package com.wangjie.binarysearch;

/**
 * @author jieshao
 * @date 2022/4/22 17:26
 *
 * 410. 分割数组的最大值
 *
 * 输入一个数组 nums 和数字 m，把 nums 分割成 m 个子数组，肯定不止一种分割方法，每种分割方法都会把 nums 分成 m 个子数组，这 m 个子数组中肯定
 * 有一个和最大的子数组，我们想要找一个分割方法，该方法分割出的最大子数组和是所有方法中最大子数组和最小的
 *
 * 此问题同 1011. 在 D 天内送达包裹的能力
 *
 * 你只有一艘货船，现在有若干货物，每个货物的重量是 nums[i]，现在你需要 m 天内将这些货物运走，请问你的货船的最小载重是多少？
 *
 * 货船每天运走的货物就是 nums 的一个子数组，在 m 天内运完就是将 nums 划分成 m 个子数组，让货船的载重尽可能小，就是让所有子数组中最大的那个子
 * 数组之和尽可能小
 */
public class Test05 {
    public int splitArray(int[] nums, int m) {
        int left = 0;
        int right = 1;
        for (int t : nums) {
            left = Math.max(left, t);
            right += t;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (f(nums, mid) <= m) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int f(int[] nums, int x) {
        int res = 0;
        for (int i = 0; i < nums.length; ) {
            int cap = x;
            while (i < nums.length) {
                if (nums[i] > cap) {
                    break;
                }
                cap -= nums[i];
                i++;
            }
            res++;
        }
        return res;
    }
}